package leetcode.problems.P5最长回文子串;

public class LongestPalindrome {
    public static void main(String[] args) {
//        System.out.println(new Solution().longestPalindrome("a"));
        int a = 147, b = 43;
        // 不使用加法计算两数之和的一半
        System.out.println((a + b) / 2);// 95
        System.out.println(a - (a - b) / 2); // 95
        System.out.println(a / 2 + b / 2); // 94
    }
}

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 1) return "";
        String ans = "";
        boolean[][] dp = new boolean[len][len];
        // 当 len > 3 时，dp[i][j] = dp[i+1][j-1] && (s[i] == s[j])
        // 表格边界：dp[i][i] = true  dp[i][i+1] = (s[i] == s[i+1])
        // i从末尾开始向前、j从i开始向后迭代
        for (int i = len - 1; i >= 0; --i) {
            for (int j = i; j < len; ++j) {
                if (i == j) {
                    dp[i][j] = true;
                } else if (i + 1 == j) {
                    dp[i][j] = s.charAt(i) == s.charAt(j);
                } else {
                    dp[i][j] = dp[i + 1][j - 1] && (s.charAt(i) == s.charAt(j));
                }
                if (dp[i][j] && ans.length() < j - i + 1) ans = s.substring(i, j + 1);
            }
        }
        return ans;
    }
}